package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

/**
 * @description:
 * 1372. 二叉树中的最长交错路径
 * 提示
 * 中等
 * 116
 * 相关企业
 * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
 *
 * 选择二叉树中 任意 节点和一个方向（左或者右）。
 * 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 * 改变前进方向：左变右或者右变左。
 * 重复第二步和第三步，直到你在树中无法继续移动。
 * 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
 *
 * 请你返回给定树中最长 交错路径 的长度。
 *
 *
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 18:10
 * @version:1.0
 */
public class 二叉树中的最长交错路径 {
    //递归，返回当前节点的左节点最大交错路径和右节点最长交错路径；
    public int longestZigZag(TreeNode root) {
        int max[] = new int[]{0};
        nodeZigZag(root,max);
        return max[0];
    }
    //第一个保存左子树最大交错路径,第二个保存右子树最大交错路径
    public int[] nodeZigZag(TreeNode node,int max[]){
        int[] nodeMax = new int[2];
        if(node.left != null){
            int [] leftNodeMax = nodeZigZag(node.left,max);
            nodeMax[0] = leftNodeMax[1]+1;
        }else{
            nodeMax[0] = 0;
        }
        if(node.right != null){
            int [] rightNodeMax = nodeZigZag(node.right,max);
            nodeMax[1] = rightNodeMax[0]+1;
        }else{
            nodeMax[1] = 0;
        }
        max[0] = nodeMax[0] > max[0]?nodeMax[0]:max[0];
        max[0] = nodeMax[1] > max[0]?nodeMax[1]:max[0];
        return nodeMax;
    }
}
